// 题目链接：https://www.acwing.com/file_system/file/content/whole/index/content/3554/

// 1.记忆化搜索
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;
int v[N], w[N];
int n, m;
int mem[N][N];

int DFS(int x, int spV)
{
    if (mem[x][spV])
        return mem[x][spV];

    int sum = 0;
    if (x > n)
        return 0;

    if (spV < v[x])
        sum = DFS(x + 1, spV);
    else
        sum = max(DFS(x + 1, spV), DFS(x, spV - v[x]) + w[x]);

    mem[x][spV] = sum;
    return sum;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    int res = DFS(1, m);
    printf("%d\n", res);

    return 0;
}

//--------------------------------------------------------------------
// 2.动态规划 + 二维数组
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;
int v[N], w[N];
int n, m;
int f[N][N];

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    for (int i = n; i >= 1; --i)
    {
        for (int j = 0; j <= m; ++j)
        {
            if (j < v[i])
            {
                f[i][j] = f[i + 1][j];
            }
            else
            {
                f[i][j] = max(f[i + 1][j], f[i][j - v[i]] + w[i]);
            }
        }
    }

    printf("%d\n", f[1][m]);

    return 0;
}

//--------------------------------------------------------------------
// 3.动态规划 + 一维滚动数组
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;
int v[N], w[N];
int n, m;
int f[N];

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    for (int i = n; i >= 1; --i)
    {
        for (int j = v[i]; j <= m; ++j)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    printf("%d\n", f[m]);

    return 0;
}